package animation.sort.algorithms;

import animation.sort.SortAnimation;
import animation.core.AlgorithmMonitorModel;

/**
 * Created by IntelliJ IDEA.
 * User: emilio
 * Date: Aug 12, 2004
 * Time: 11:57:23 AM
 * To change this template use File | Settings | File Templates.
 */
public class QuickSort
        extends SortAnimation
{
    public String toString()
    {
        return "Quick Sort";
    }

    protected void sort(int array[])
            throws Exception
    {
        sort(array, 0, array.length - 1);
        unmarkAll();
    }

    void sort(int array[], int low, int high)
            throws Exception
    {
        if (low < high) {
            markBox(low, high);
            int pos = partition(array, low, high);
            sort(array, low, pos - 1);
            sort(array, pos + 1, high);
        }
    }

    protected int partition(int[] array, int low, int high)
            throws Exception
    {
        monitorModel.setVariableValue("left", low);
        monitorModel.setVariableValue("right", high);
        int i = low - 1;
        int j = high;
        monitorModel.setVariableValue("j", "right="+j);
        monitorModel.setVariableValue("i", "left-1="+i);
        monitorModel.setVariableValue("pivot", "right="+high);
        for (; ;) {
            monitorModel.setVariableValue("i", i+1);
            while (greater(array, high, ++i)) {
                monitorModel.setVariableValue("i", i+1);
            }

            monitorModel.setVariableValue("j", j-1);
            while (greater(array, --j, high)) {
                if (j == low) {
                    break;
                }
                monitorModel.setVariableValue("j", j-1);
            }
            if (i >= j) {
                break;
            }
            swap(array, i, j);
        }
        swap(array, i, high);
        return i;
    }

    protected void registerSpecificVariables(AlgorithmMonitorModel monitorModel) {
        monitorModel.registerVariable("pivot", "undefined");
        monitorModel.registerVariable("i", "0");
        monitorModel.registerVariable("j", "0");
        monitorModel.registerVariable("left", "0");
        monitorModel.registerVariable("right", "0");
    }

}
